The present invention relates to log structured arrays for storage subsystems, and more particularly to preventing deadlock in log structured arrays.
In a storage subsystem, a redundant array of inexpensive disks, RAID, is one solution to I/O (input/output) bottleneck problems. RAID typically increases disk bandwidth through parallelism for accessing data and provides high data availability through redundancy. One problem associated with some levels of RAID is the write penalty; a write operation actually requires two disk reads (of old data and parity) and two disk writes (of updated data and the newly calculated parity). Log Structured Array, (ISA), writes all customer data to disk sequentially in a log-like structure, and enables RAID to support data compression. The amount of compression achieved is dependent on the actual data values. After a piece of data is modified, it may not compress to the same number of bytes and thus will not fit into the space originally allocated to it. This problem is encountered in any storage system that assigns a piece of data to a disk fixed location; LSA avoids this problem, since updated data is written to the end of the log structure.
Through LSA, a logical track, LT, which is the typical unit accessed by I/O programs, is allowed to be updated to a different location on disk. Since the physical address of a logical track changes over time, a directory, called LSA directory, is necessary to keep track of the current LT""s physical address on the array. Each directory entry also records the logical track""s current length, as this may vary with compression.
The log structured array consists of N+P+S physical disk drives, where N is the number of HDDs"" (hard disk drives) worth of physical space available for customer data, P is the number of HDDs"" worth of physical space for parity data, and S is the number of HDDs"" worth of physical space for spare drives. Each HDD is divided into large consecutive areas called segment columns. Typically, a segment column is as large as a logical cylinder. Corresponding segment columns from the N+P+S HDDs constitute a segment. The array has as many segments as there are segment columns on a HDD disk in the array. An example of the layout for such a system is shown in FIG. 1. In a RAID-5 configuration, one of the segment columns of a segment contains the parity of the remaining data segment columns of the segment.
Referring to FIG. 1, the storage for the partition 52 is arranged as segments 56, where each segment has N data segment columns 58 and one parity segment column 59. The logical tracks 60 are stored within segment columns. A segment directory 62 contains information on each of the logical tracks in the segment which is used during garbage collection and recovery procedures. The segment directory 62 is stored in a small number of sectors out of a segment""s total disk space. As shown, the entire segment directory resides in one same segment column in each of the segments. Alternatively, the segment directory can be spread among the devices. In a RAID-5 system, parity is distributed among the devices as shown.
A segment column is defined as an arbitrary number of contiguous physical tracks as described above. Typically it is desirable to define a segment column to be the same size as a logical cylinder. The collection of disk recording areas comprising corresponding segment columns from each of the HDDs forms what is called a segment.
LSA segments are categorized as one of the following types: free, which refers to a segment that contains no valid data; open, which refers to a segment that is available to hold LTs being destaged; closed, which refers to a segment containing some valid data, but to which no destaged data can be further assigned; and being garbage collected, GC, which refers to a closed segment that is currently being garbage collected, as discussed hereinbelow. A closed segment consists of xe2x80x98livexe2x80x99 LTs and xe2x80x98holesxe2x80x99. The former are LTs that were assigned to the segment during the segment""s open phase and still reside in the segment. The latter is space vacated by LTs that were assigned to the segment but have subsequently been updated and assigned to different open segments. A closed segment""s occupancy is the sum of the lengths of the segment""s live tracks.
A destage operation provides for the LTs in a logical cylinder to be destaged together from a cache within the storage subsystem to a storage device to enhance the seek affinity of sequential accesses. A logical cylinder is typically called a neighborhood, and a group of logical tracks in a logical cylinder destaged together is called a neighborhood in destage (NID) or neighborhood destage request. Destaging a neighborhood essentially involves the following steps:
1. The neighborhood in destage is assigned to an open segment.
2. An open segment remains available to accept other neighborhoods in destage until it is deemed full enough to close in accordance with a desired algorithm.
3. The data and parity of the segment is written to disk before the segment is considered closed.
4. Each LT in the open segment has an entry in the segment directory that describe the LT""s location in the segment. The segment directory is written on disk, as part of the segment.
An LT in a closed segment may be updated and destaged again, at which time it is assigned to another open segment. This causes the previous copy of the LT to become obsolete, thus forming a xe2x80x98holexe2x80x99 in the closed segment. Garbage collection (GC) is the process of reclaiming xe2x80x98holesxe2x80x99 in closed segments. GC is started when the number of free segments falls below a certain threshold.
The process of garbage collecting a segment involves reading the segment""s directory from disk, then scanning each segment directory entry and comparing the LT""s address as indicated by the segment directory entry with the address as indicated by the LSA directory entry. If the two entries match, then the LT still resides in the segment and is considered xe2x80x98livexe2x80x99. All the live LTs are then read from disk into memory and sorted by neighborhood. These neighborhoods in destage then proceed to be destaged in the same manner as described above. These NIDs are assigned to open segments; when such open segments close successfully, the NIDs are garbage collected, thus decreasing the occupancy of the segments in which the NIDs previously resided. When a segment""s occupancy declines to zero, either as a result of garbage collection or as a result of movement of tracks from normal destage activity, the segment becomes free.
The following problem exists during concurrent garbage collection and destaging. The process of garbage collecting a segment requires that at least one free segment exists in order to serve as the new home for live logical tracks being moved from the garbage collected segment. If no free segments are available to hold garbage collected LTs, then a deadlock may occur: future destage operations stall because there are no free segments to hold LTs that are destaged; only the GC process can produce free segments, since segments can no longer become empty through the movement of updated LTs to new segments; however, the GC process cannot proceed without a free segment. A remote possibility exists that LTs newly assigned to open segments at the time the LSA exhausts its supply of free segments will free one or more segments when those open segments eventually close and the NIDs are destaged. However reliance on this possibility does not ensure the correct functioning of the log-structured system.
Accordingly, a need exists for a method and system of preventing deadlock during garbage collection in a log structured array. The present invention addresses such a need.
The present invention provides aspects for preventing deadlock in a log structured array. In an exemplary method aspect, and system for providing same, the method includes monitoring available segments to determine when to reserve an open segment, identifying a process type requesting access to the open segment, and limiting access to one process type for a reserved segment. Limiting access further includes limiting access to a garbage collection process.
Through the present invention, stalls of destage operations are avoided by eliminating deadlocks that can occur because of contention over free segments between garbage collection and destage processes. Control of a last free segment for exclusive use by a garbage collection process effectively maintains production of free segments via garbage collection techniques. These and other advantages of the aspects of the present invention will be more fully understood in conjunction with the following detailed description and accompanying drawings.